﻿
//#include <stdio.h>
//#include <stdlib.h>
//#define MAXSIZE 100
//typedef double DataType;
//typedef struct
//{
//	DataType data[MAXSIZE];
//	int top;
//}SeqStack,*PSeqStack;
////初始化
//PSeqStack Init_SeqStack()
//{
//	PSeqStack S;
//	S = (PSeqStack)malloc(sizeof(SeqStack));
//	S->top = -1;//方便入栈
//	return S;
//}
//
////判栈空
//int Empty_SeqStack(PSeqStack S)
//{
//	if (S->top == -1) {
//		return 1;//栈为空
//	}
//	else
//	{
//		return 0;//栈不为空
//	}
//}
////入栈
//int In_SeqStack(PSeqStack S,DataType *x)//体会 int 的好了
//{
//	if (S->top+1 == MAXSIZE)//S->top初始为-1
//	{
//		printf("栈已满!");
//		return 0;
//	}
//	S->data[S->top + 1] = *x;
//	S->top++;
//	return 1;
//}
////出栈
//int Out_SeqStack(PSeqStack S)
//{
//	DataType x;
//	if (S->top == -1)
//	{
//		//printf("栈为空!");
//		return 0;
//	}
//	x = S->data[S->top];
//	S->top--;
//	return 1;
//}
////取栈顶元素
//DataType GetTop_SeqStack(PSeqStack S)//只传出不进，不传入，所以要使用值传递
//{
//	DataType x;
//	if (S->top == -1)
//	{
//		//printf("栈为空!");
//		return;
//	}
//	x=S->data[S->top];
//	return x;
//}
////销毁
//void Destroy_SeqStack(PSeqStack *S)
//{
//	if(*S)//如果存在
//		free(*S);
//	*S = NULL;
//}
//
////typedef char DataType;
//int conversion(int n, int r)
//{
//	char ch[16] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
//	PSeqStack S;
//	DataType x;
//	if (r<=1)
//	{
//		printf("基数不能为0或1");
//		return 0;
//	}
//	S = Init_SeqStack();
//	if (!S)
//	{
//		printf("初始化失败!");
//		return 0;
//	}
//	while (n)
//	{
//		In_SeqStack(S, ch[n%r]);
//		n /= r;
//	}
//	while (!Empty_SeqStack(S))
//	{
//		x=Out_SeqStack(S);
//		printf("%c", x);
//	}
//	Destroy_SeqStack(&S);
//}
//
//int IsNum(char c)
//{
//	if (c >= '0'&&c <= '9') return 1;//是数字返回1
//	else return 0;
//}
//DataType postfix_exp(char *A)
//{
//	PSeqStack S;
//	DataType Result, a, b, c;
//	char ch;
//	ch = *A++;
//	S = Init_SeqStack();//初始化
//	while (ch!='#')
//	{
//		if (IsNum(ch)) {
//			DataType s = 0;
//			s = ch - '0';
//			In_SeqStack(S, &s);
//		}
//		else
//		{
//			b=Out_SeqStack(S);
//			a=Out_SeqStack(S);
//			switch (ch)
//			{
//			case '+':c = a + b; break;
//			case '-':c = a - b; break;
//			case '*':c = a * b; break;
//			case '/':c = a / b; break;
//			case '%':c = (int)a % (int)b; break;
//			}
//			In_SeqStack(S, &c);
//		}
//		ch = *(A++);
//	}
//	Result = GetTop_SeqStack(S);
//	Destroy_SeqStack(S);
//	return Result;
//}
//void test01()
//{
//	conversion(16, 16);
//}
//void test02()
//{
//	char A[] = "1285-*+42/-#";
//	printf("%f", postfix_exp(A));
//}
//void test03(char *A)
//{
//	int i = 0;
//	char ch;
//	while (*A != '\0')
//	{
//		ch = *A++;
//		printf("%c", ch);
//		i++;
//	}
//}
//int main()
//{
//	test02();
//	//char *A = "(2 + 4) * 2 + 3";
//	//test03(A);
//	return 0;
//}

//顺序表栈实现数置转换

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAXSIZE 100
typedef char DataType;
typedef double DataType_d;
//定义结构体
//template<>
//template <sturct T>

typedef struct
{
	DataType data[MAXSIZE];
	int top;
}SeqStack, *PSeqStack;
//初始化空栈
PSeqStack Init_SeqStack()
{
	PSeqStack S;
	S = (PSeqStack)malloc(sizeof(SeqStack));
	if (S)
		S->top = -1;
	return S;
}
//判断空栈
int Empty_SeqStack(PSeqStack S)
{
	if (S->top == -1)
		return 1;
	else
		return 0;
}
//入栈
int Push_SeqStack(PSeqStack S, DataType x)
{
	if (S->top == MAXSIZE - 1)
		return 0;//栈已满，不能入栈
	else
	{
		S->top++;
		S->data[S->top] = x;
		return 1;
	}
}
//出栈
int Pop_SeqStack(PSeqStack S, DataType *x)
{
	if (Empty_SeqStack(S))
		return 0;//空栈，不能能出栈
	else {
		*x = (S->data[S->top]);
		S->top--;
		return 1;
	}
}
//取栈顶元素
int GetTop_SeqStack(PSeqStack S, DataType *x)
{
	if (Empty_SeqStack(S))
		return 0;//空栈，不能出栈
	else {
		*x = S->data[S->top];
		return 1;
	}
}
//销毁栈
void Destroy_SeqStack(PSeqStack *S)
{
	if (*S)
		free(*S);
	*S = NULL;
	return;
}
//打印栈
int Print_SeqStack(PSeqStack S)
{
	if (Empty_SeqStack(S))
		return 0;//空栈，不能打印
	else {
		//printf("打印全栈\n");
		for (int i = S->top; i >= 0; i--) {
			printf("%c", S->data[i]);
		}
		return 1;
	}
}



typedef struct
{
	DataType_d data[MAXSIZE];
	int top;
}SeqStack_d, *PSeqStack_d;
//初始化空栈
PSeqStack_d Init_SeqStack_d()
{
	PSeqStack_d S;
	S = (PSeqStack_d)malloc(sizeof(SeqStack_d));
	if (S)
		S->top = -1;
	return S;
}
//判断空栈
int Empty_SeqStack_d(PSeqStack_d S)
{
	if (S->top == -1)
		return 1;
	else
		return 0;
}
//入栈
int Push_SeqStack_d(PSeqStack_d S, DataType_d x)
{
	if (S->top == MAXSIZE - 1)
		return 0;//栈已满，不能入栈
	else
	{
		S->top++;
		S->data[S->top] = x;
		return 1;
	}
}
//出栈
int Pop_SeqStack_d(PSeqStack_d S, DataType_d *x)
{
	if (Empty_SeqStack_d(S))
		return 0;//空栈，不能能出栈
	else {
		*x = (S->data[S->top]);
		S->top--;
		return 1;
	}
}
//取栈顶元素
int GetTop_SeqStack_d(PSeqStack_d S, DataType_d *x)
{
	if (Empty_SeqStack_d(S))
		return 0;//空栈，不能出栈
	else {
		*x = S->data[S->top];
		return 1;
	}
}
//销毁栈
void Destroy_SeqStack_d(PSeqStack_d *S)
{
	if (*S)
		free(*S);
	*S = NULL;
	return;
}
//打印栈
int Print_SeqStack_d(PSeqStack_d S)
{
	if (Empty_SeqStack_d(S))
		return 0;//空栈，不能打印
	else {
		//printf("打印全栈\n");
		for (int i = S->top; i >= 0; i--) {
			printf("%f", S->data[i]);
		}
		return 1;
	}
}

//数值转换问题//整数部分，小数部分还不知道咋整呢？？？？
//typedef int DataType;  
int conversion(int n, int r)//r:进制数基数  n:要转换的数
{
	PSeqStack S;//定义一个栈
	//DataType x;//定义一个数据节点
	if (!r)
	{
		printf("基数不能为0!\n");
		return 0;
	}
	S = Init_SeqStack();//对栈进行初始化
	if (!S) {
		printf("栈初始化失败！\n");
		return 0;
	}
	while (n)
	{
		Push_SeqStack(S, n%r);//取余，依次压入栈内
		n = n / r;//取整
	}
	//while (!Empty_SeqStack(S))
	//{
	//	Pop_SeqStack(S, &x);
	//	//printf("%d", x);
	//}
	Print_SeqStack(S);
	Destroy_SeqStack(&S);
}


//后缀表达式求值
//判断是数，还是操作符
int IsNum(char c)
{
	if (c >= '0'&&c <= '9') return 1;//是数字返回1
	else return 0;
}  
DataType_d postfix_exp(char *A)
{
	PSeqStack_d S;
	DataType_d Result, a, b, c;
	char ch;
	ch = *A++;
	S = Init_SeqStack_d();//初始化
	while (ch!='#')
	{
		if (IsNum(ch)) {
			Push_SeqStack_d(S, ch - '0');
		}
		else
		{
			Pop_SeqStack_d(S, &b);
			Pop_SeqStack_d(S, &a);
			switch (ch)
			{
			case '+':c = a + b; break;
			case '-':c = a - b; break;
			case '*':c = a * b; break;
			case '/':c = a / b; break;
			case '%':c = (int)a % (int)b; break;
			}
			Push_SeqStack_d(S,c);
		}
		ch = *(A++);
	}
	GetTop_SeqStack_d(S,&Result);
	Destroy_SeqStack_d(&S);
	return Result;
}

//中缀表达式转后缀表达式
//求优先级操作
int priority(char op)
{
	switch (op)
	{
	case '#':return 1; break;//1级
	case ')':return 2; break;//2级
	case '+':
	case '-':return 3; break;//3级
	case '*':
	case '/':return 4; break;//4级
	case '(':return 5; break;//5级
	default:
		return 0;
		break;
	}
}

int infix_exp_value(char * infixexp, char * postfixexp)//infixexp中缀   postfixexp后缀
{
	PSeqStack S;//这个栈是用装符号的栈，用于解决优先级的问题
	char c, w, topelement;//c永远是栈顶元素
	S = Init_SeqStack;
	if (!S)
	{
		pritnf("栈初始化失败！");
		return 0;
	}
	Push_SeqStack(S, '#');//这才入一个
	w = *infixexp;//w是字符，不是指针？？
	while ((GetTop_SeqStack(S,&c),c) !='#'||w!='#')//栈顶元素返回给c   逗号表达式
	{
		if (IsNum(w))//如果是数字，就直接给到字符串
		{
			*postfixexp = w;
			postfixexp++;
			w = *(++infixexp);//读取下一个字符
		}
		else//如果w符号
		{
			if ((GetTop_SeqStack(S, &c), c) == '('&&w == ')')//去括号，得到的w是算符，且发生‘（’ 和‘）’的匹配，就把括号中的字符给到后缀表达式的字符串
			{
				Pop_SeqStack(S, &topelement);//用toplement吸收掉‘（’
				w = *(++infixexp);//读取下一个字符
			}
			else//如果读的w是算符，且不发生‘（’ 和‘）’的匹配
			{
				//
				if ((GetTop_SeqStack(S, &c), c) == '(' || priority((GetTop_SeqStack(S, &c), c)) < priority(w))
				{//翻译：如果栈顶元素是'('或者栈顶元素的优先级小于当前字符，就把w压入栈内，然后读取下一个字符
					Push_SeqStack(S, w);
					w = *(++infixexp);
				}
				else
				{
					Pop_SeqStack(S, &topelement);//出栈
					*postfixexp = topelement;
					postfixexp++;
				}
			}
		}
	}
	*postfixexp = '#';
	*(++postfixexp) = '\0';//结果就直接是值传递给了postfixexp 他是一个char *postfixexp
	Destroy_SeqStack(&S);
	return 1;
}

//数制转换测试
void test01()
{
	conversion(16, 16);
}
//后最表达式测试
void test02()
{
	char A[] = "1285-*+42/-#";
	printf("%.2f", postfix_exp(A));
}

//中缀转后缀

void test03()
{
	char *infixexp = "(4*5)-20/2#";
	char *postfixexp;
	postfixexp = (char*)malloc(sizeof(char));
	infix_exp_value(infixexp, postfixexp);
	puts(postfixexp);
	//printf("%.2f", postfix_exp(postfixexp));
}


int main()
{
	test03();
}

